#include <iostream>
#include "common_list.h"
#include <vector>

using namespace std;
class Solution {

public:
    ListNode *do_merge(ListNode *h1, ListNode *h2) {
        ListNode *temp = new ListNode;
        ListNode *ptr = temp;

        while(h1 && h2) {
            if (h1->val < h2->val) {
                ptr->next = h1;
                h1 = h1->next;
            } else {
                ptr->next = h2;
                h2 = h2->next;
            }
            ptr = ptr->next;
        }

        if (h1) {
            ptr->next = h1;
        }
        if (h2) {
            ptr->next = h2;
        }
        return temp->next;
    }

    ListNode *split(vector<ListNode*> &vec, int l, int r) {
        int mid = l + (r-l)/2;
        if (r <= l) {
            return vec[mid];
        }
        ListNode *lh = split(vec, l, mid);
        ListNode *rh = split(vec, mid + 1, r);
        auto ret = do_merge(lh, rh);
        return ret;
    }
    ListNode *mergeKList2(vector<ListNode*> &vec) {
        // 归并方法
        return split(vec, 0, vec.size()-1);
    }
    ListNode *mergeKList(vector<ListNode*> &vec) {
        ListNode* temp = new ListNode;
        ListNode* ptr = temp;
        bool all_null = false;
        
        while (!all_null) {
            int min_val = 9e8;
            int min_idx = 0;
            all_null = true;
            for (int i = 0; i < vec.size(); i++) {
                if (vec[i]) {
                    all_null = false;
                    if (vec[i]->val < min_val) {
                        min_idx = i;
                        min_val = vec[i]->val;
                    }
                }
            }
            if (!all_null) {
                ptr->next = vec[min_idx];
                ptr = ptr->next;
                vec[min_idx] = vec[min_idx]->next; 
            }
        }
        return temp->next;
    }
};


int main(void)
{
    cout << "合并k个链表" << endl;

    int val1[] = {1, 4, 6};
    int val2[] = {2,  4, 9};
    int val3[] = {-1, 12};

    auto l10 = generate_list_val(sizeof(val1)/sizeof(int), val1);
    auto l20 = generate_list_val(sizeof(val2)/sizeof(int), val2);
    auto l30 = generate_list_val(sizeof(val3)/sizeof(int), val3);

    auto l11 = generate_list_val(sizeof(val1)/sizeof(int), val1);
    auto l21 = generate_list_val(sizeof(val2)/sizeof(int), val2);
    auto l31 = generate_list_val(sizeof(val3)/sizeof(int), val3);

    print_list(l10);
    print_list(l20);
    print_list(l30);

    cout << "普通合并法" << endl;
    vector<ListNode*> vec0 = {l10, l20, l30};
    auto new_list = Solution().mergeKList(vec0);
    print_list(new_list);

    cout << "归并法" << endl;
    vector<ListNode*> vec1 = {l11, l21, l31};
    auto new_list2 = Solution().mergeKList2(vec1);
    print_list(new_list2);


    return 0;
}